#include <iostream>  
#include <memory>  // 引入智能指针头文件  
  
using namespace std;  
  
struct ListNode {  
    int val;  
    std::unique_ptr<ListNode> next;  // 使用智能指针代替原始指针  
    ListNode(int x) : val(x), next(nullptr) {}  
};  
  
// 在链表头插入一个新节点  
void insert(ListNode* &head, int val) {  
    std::unique_ptr<ListNode> node = std::make_unique<ListNode>(val);  // 使用智能指针创建新节点  
    node->next = std::move(head);  // 将原头节点移动到新节点的后面  
    head = std::move(node);  // 将新节点移动到头节点位置  
}  
  
// 删除链表中的指定节点  
void deleteNode(ListNode* &head, int val) {  
    if (head == nullptr) return;  // 如果链表为空，直接返回  
    if (head->val == val) {  // 如果头节点就是要删除的节点，直接将头节点移动到下一个节点  
        head = std::move(head->next);  
        return;  
    }  
    ListNode* prev = head;  // 用于遍历链表，找到要删除的节点的前一个节点  
    ListNode* cur = head->next;  // 从头节点的下一个节点开始遍历  
    while (cur != nullptr && cur->val != val) {  
        prev = cur;  
        cur = cur->next;  
    }  
    if (cur != nullptr) {  // 如果找到要删除的节点  
        prev->next = std::move(cur->next);  // 将前一个节点的next指针指向要删除节点的下一个节点  
    }  
}  
  
// 遍历链表，输出所有节点的值  
void traverse(ListNode* head) {  
    ListNode* cur = head;  
    while (cur != nullptr) {  
        cout << cur->val << " ";  
        cur = cur->next.get();  // 使用get()函数获取下一个节点的原始指针  
    }  
    cout << endl;  
}  
  
int main() {  
    // 创建一个空链表  
    ListNode* head = nullptr;  
  
    // 向链表中插入一些节点  
    insert(head, 1);  
    insert(head, 2);  
    insert(head, 3);  
    insert(head, 4);  
    insert(head, 5);  
  
    // 遍历链表，输出所有节点的值  
    traverse(head);  
  
    // 删除链表中的节点  
    deleteNode(head, 3);  
  
    // 再次遍历链表，输出所有节点的值  
    traverse(head);  
  
    return 0;  
}